# koroFileHeader at Yungoal acer
# Create: 2021-09-07 10:03:13
# LastEdit: 2021-09-07 10:11:29
"""https://leetcode-cn.com/problems/maximum-subarray/"""
__author__ = '749B'

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_f = nums[0]
        pre_f = nums[0]
        for i in range(1, len(nums)):
            # 以当前位置为结尾的最大子序列的和
            #     当前数字之前的总和为负数，之后就不用再往前找了
            pre_f = max(pre_f + nums[i], nums[i])
            max_f = max(pre_f, max_f)
        return max_f

